# 从中序与后序遍历序列构造二叉树

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        return self.build(postorder, inorder)

    def build(self, postorder, inorder):
        if not postorder:
            return None
        root = postorder[-1]
        node = TreeNode(root)
        # 根据中序遍历分为左右子树
        global i
        for i in range(len(inorder)):
            if inorder[i] == root:
                break
        left_inorder = inorder[0:i]
        right_inorder = inorder[i+1:len(inorder)]
        # 把后序也分为左右子树
        left_postorder = postorder[0:len(left_inorder)]
        right_postorder = postorder[len(left_inorder):len(postorder)-1]
        node.left = self.build(left_postorder, left_inorder)
        node.right = self.build(right_postorder, right_inorder)
        return node
